Computer graphic images are often made up of line primitives. Line primitives can represent many types of objects in computer graphic systems. Such objects can be, for example, electrical, mechanical, chemical, architectural, or artistic in nature. Most graphic systems represent the object on the display screen by a set of data which represents the coordinates of the line primitives. For example, in a two-dimensional display, these coordinate data sets are sets of values, such as x.sub.1,y.sub.1 ; x.sub.2,y.sub.2 ; etc., which represent each end-point x-y coordinate location of each line primitive contained in the display; more specifically, the coordinate data x.sub.1,y.sub.1 corresponds to one end-point of a line primitive, and the companion coordinate data x.sub.2,y.sub.2 corresponds to the other end-point of the same line primitive. The quantity of line primitives representing the images on a display screen can be extraordinarily large depending on the number and complexity of objects being displayed. Typically, in design systems, the quantity of line primitives corresponding to the objects shown on a display screen can at any given time range from thousands to hundreds of thousands.
Selecting an object on a screen is commonly referred to as "picking". The picking of an object is generally enabled using a pick marker to select the object on the displayed image. The pick marker used in display systems can take the form of any symbol, such as an arrow, star, polygon, rectangle, line etc.; and a user can move the pick marker about a display screen by various means, such as using a "mouse", light pen, keypad, etc. "Pick correlation" refers to the task of determining if the pick marker has a "hit" on, or has picked, a line primitive (and thus the object to which the line primitive corresponds) in the displayed image.
Currently, two methods are used for pick correlation, the so-called analytical method and the so-called clipping method. An example of an analytical method is disclosed in U.S. Pat. No. 4,698,625, to McCaskill et al. which relates to a technique for facilitating the selection of a graphic object on a display screen by a user. When a pointing cursor is brought to within a predetermined distance of a graphic object, the point on the graphic object closest to the pointing cursor is highlighted to show that the graphic object would be selected if the select button is depressed. If the user then depresses the select button, the entire graphic object is highlighted to indicate that it has been selected.
In contrast to analytical methods, clipping methods generally utilize a pick correlation approach whereby a window or an aperture is made to correspond to a pick marker. Such a window or aperture is referred to as a pick window or pick aperture. The pick window used in clipping methods may sometimes be invisible to a user. Typically, the clipping method rejects each line primitive in a display which does not have at least a portion within, or at least touching or in contact with, the pick window. The line primitive is clipped against the edges or boundaries which define the pick window, i.e., an evaluation is made to determine the intersection between the line primitive and the edges of the pick window, and if the clipping results in at least a portion of the line primitive determined as being within, or at least touching or contacting, the pick window (such line primitive being regarded as being "visible" within the pick window), then the line primitive is picked or accepted.
In order to outline the difficulties of pick correlation, reference is now made to FIG. 1. A rectangular pick window 10 is used to illustrate the difficulties, and it is apparent that similar, and additional, difficulties are encountered for pick correlation for a diamond shaped pick window. A diamond shall be defined herein as a four-sided polygon having sides of equal length, and having one diagonal which is parallel to the x axis and its other diagonal parallel to the y axis; and a diagonal is defined as a line segment which connects two opposite vertices or corner points of the diamond. Four line primitives having end-points labelled as AB, CD, EF and GH are shown. It can be seen that both end-points of line primitive AB are within the pick window 10; one end-point C of line primitive CD is within the pick window 10 and the other end-point D is outside the pick window 10; and both end-points of line primitives EF and GH are outside the pick window 10. Using well known methods of clipping, such as the Cohen-Sutherland method outlined hereinbelow, line primitives which either have both of its end-points or one of its end-points within or contacting the pick window 10 can be trivially accepted, such as line primitive CD and line primitive AB. In other words, the conclusion for either line primitive CD or line primitive AB being within the pick window 10 can be relatively easily derived using conventional techniques. However, the pick decision for line primitives which have both of its end-points outside of the pick window 10, such as line primitives EF and GH, is a difficult determination and typically involves extensive, time-consuming computations.
Several prior art pick correlation methods are discussed in the textbook "Computer Graphics--Principles and Practice" by Foley, vanDam, Feiner and Hughes, Second Edition, 1990, Published by Addison Wesley, see specifically, pp. 48-50, 338-339, 111-124 and 925-928.
A basic line pick correlation technique, referred to herein as the "brute force" method, allows for testing of all line primitives, trivial and non-trivial cases. In the brute force method, line primitives are tested against each edge of the pick window by simultaneously solving line equations. More specifically, a rectangular or diamond shaped pick window, can be described by four line equations, wherein each line equation corresponds to an edge of the pick window. The equation of each pick window edge and the equation of the line primitive are simultaneously solved for determining if common intersect points exist. The intersect points are then tested to determine if they are visible within the pick window, and the line primitive can thus be accepted or rejected. The brute force method requires performing several mathematical operations, including multiplication, division and comparison, for each pick window edge/line primitive pair. The task of testing thousands of line primitives can be substantial and time-consuming even for a computer; and, in order to speed up division and multiplication operations, complicated and expensive processors capable of performing floating point operations, as opposed to simpler fixed point operations, are required. In this regard, implementing fixed point operations, and avoiding floating point operations, generally leads to a simpler and more efficient implementation. Regardless of the particular platform being used, floating point operations are inherently more expensive than fixed point operations. More particularly, floating point numbers have two components that need to be considered, an mantissa and an exponent, as opposed to fixed point numbers which can be exactly represented in a single entity. Further, in contrast to fixed point operations, floating point operations require rounding operations to minimize the inaccuracies inherent in floating point calculations. For example, floating point multiplication involves not only multiplication of the mantissas, but also addition of the exponents; and floating point addition requires three distinct stages, normalization of the mantissas based on the exponents, followed by the actual addition, and then a post normalization of the result. See, generally, "Computer Organization and Architecture, Principles of Structure and Function", Second Edition, Macmillan Publishing Company, pages 276-283, and "Design of the IBM RISC System/6000 Floating Point Execution Unit", by R. K. Montoye et al., IBM Journal of Research and Development, Vol. 34, No. 1, January 1990, pages 59-70, for discussion on floating point arithmetic.
Further, difficulties are encountered when testing vertical line primitives using the brute force method. Vertical line primitives have an infinite slope, and simultaneous solving of equations becomes complicated since division by zero for the slope is required.
The Cohen-Sutherland (C-S) technique ("Computer Graphics--Principles and Practice" by Foley, et al., 1990 Addison Wesley Publishers, pp. 112-117) is another method of pick correlation. As an example, the C-S method, and the difficulties inherent therewith, shall be described below with respect to a rectangular pick window. However, it should be understood that applying the C-S method to a diamond pick window is more difficult, and involves additional complexities, as compared to applying the C-S method to a rectangular pick window. In the C-S method, depending on the location of the end-points of a line primitive with respect to the pick window, each of its end-points is assigned a particular four digit code, referred to as outcode. Referring now to FIG. 2, a rectangular pick window 20 is centered at the origin 0,0 of an x-y coordinate system. The area not within the pick window 20 is divided by dashed lines into eight different outer regions. Including the inner region of the pick window 20, there are a total of nine different regions that need to be considered in determining the location of an end-point of a line primitive. Each of these nine regions has a unique four bit outcode assigned thereto, and these region outcodes are used for comparing to the outcode of the end-points for determining the location of the end-point.
In accordance with the C-S method, each bit of the outcode of an end-point is chosen based on the coordinate value of the end-point. That is, if the y coordinate of the end-point is larger than y.sub.max, then the first bit of the outcode for the end-point is 1, otherwise the first bit is 0; if the y coordinate of the end-point is smaller than Y.sub.min, then the second bit of the outcode for the end-point is 1, otherwise the second bit is 0; if the x coordinate of the end-point is larger than x.sub.max, then the third bit of the outcode for the end-point is 1, otherwise the third bit is 0; and if the x coordinate of the end-point is smaller than x.sub.min, then the fourth bit of the outcode for the end-point is 1, otherwise the fourth bit is 0; where x.sub.max, x.sub.min, y.sub.max and y.sub.min define the maximum and minimum x and y coordinates of the pick window 20 edges.
The outcodes of the end-points of a line primitive are compared with the outcodes assigned to each of the nine different regions. If both end-points of a line primitive have an outcode of 0000 then the line primitive is visible within the pick window 20, and the line primitive is trivially accepted. If both end-point outcodes of a line primitive has a bit with a value of 1 in an identical bit position, then both end-points are in one or more regions outside of the same extended edge of the pick window and the line primitive is trivially rejected. For example, if the first bit of both end-point outcodes has a value of 1, then it is known that the line primitive is in the region(s) outside of the extended upper edge of the pick window, and the line primitive can be trivially rejected. For all other cases, the line primitive may intersect at least one edge of the pick window 20. Additional steps and calculations must be performed for such a determination. In this regard, the outcode of an end-point in one of the outer regions is clipped against an edge of the pick window 20 using the brute force method to determine if there is an intersect point. If an intersect point is found, the portion of the line primitive from the intersect point to the subject outer end-point is rejected as being outside of the pick window 20, and this portion of the line primitive is disregarded by replacing the subject outer end-point with the intersect point, and the original line primitive is now replaced by a modified line primitive for further testing. The intersect point is then assigned an outcode, and the modified line primitive is subjected to the trivial test. If the modified line primitive cannot be trivially accepted or rejected using the trivial test, then one of its end-points which is in an outer region is chosen and replaced by a new intersect point for clipping with another pick window edge, again, using the brute force method, and thus, once another intersect point is found, the line primitive is again redefined and subjected to the trivial test. This process is reiterated, if required, until clipping with all pick window edges is completed.
The Cohen-Sutherland technique is considered to be an improvement for trivial testing of line primitives. However, for the line primitives that cannot be successfully tested using the trivial accept/reject criteria enunciated by Cohen-Sutherland, clipping of the line primitive using the brute force method is required before retesting with the trivial test, and the brute force method, as discussed above, undersirably requires solving simultaneous equations and performing numerous floating point multiplication and division operations. Compared to the basic brute force technique, the C-S method has reduced the number of line primitives which actually require the brute force method by allowing certain line primitives to be trivially accepted or rejected. However, using the C-S method, multiple clippings may be required for those line primitives which are subjected to the brute force method. Further, the C-S technique disadvantageously performs clipping operations in a fixed manner, oftentimes resulting in the performance of unnecessary, extraneous clipping operations.
Duvanenko et al. (Dr. Dobbs Journal, July, 1990, pp. 36-45, 98,100) discloses a technique which attempts to speed up the Cohen-Sutherland method. In Duvanenko et al., calculation of the slope and inverted slope is performed only once per line primitive. Duvanenko et al. discloses optimizing the C-S method by omitting certain boundary or edge comparisons so that the total number of floating point operations is reduced. However, even with the reduction, the Duvanenko et al. method still requires a significant number of floating point operations to be performed.
Two additional methods are the Cyrus-Beck method and the Liang and Barsky method, "Computer Graphics--Principles and Practice", by Foley, et al., 1990 Addison Wesley Publishers, pp. 117-124. The Cyrus-Beck method implements a parametric line algorithm which finds the value of a parameter t in the parametric representation of the line primitive for the point at which that line primitive intersects the infinite line on which the clip pick window edge lies. Since all edges are somewhere intersected by the line primitive, four values of t can be calculated. A series of comparisons is then used to determine if any of the four values of t correspond to an "actual" intersection of the edge of the pick window. The coordinate values for the one or two actual intersections can then be calculated. Thus, the Cyrus-Beck method saves time as compared to the Cohen-Sutherland method in that the Cyrus-Beck approach avoids the repetitive looping needed to clip to multiple edges, and the actual calculation of the coordinates of the intersect points is postponed until needed. The Liang and Barsky method is considered to be an improvement over the Cyrus-Beck technique because the Liang and Barsky technique examines each t value as it is generated, so that some line primitives can be rejected before all four t values have been computed. Although Cyrus-Beck and Liang and Barsky offer some degree of improvement, both of these methods still require numerous floating point multiplication and division operations to be performed.
The Nicholl et al. method as disclosed in "An Efficient New Algorithm for 2-D Line Clipping: Its Development and Analysis", ACM, Computer Graphics, Volume 21, Number 4, July 1987, pp. 253-262, uses an alternate approach to improve the non-trivial testing of the line primitives that cannot be tested by the Cohen-Sutherland method of trivial testing. The Nicholl et al. method involves dividing the two-dimensional space of the display screen by connecting a line from a selected end-point of the line primitive to each of the four corners of the pick window. By subdividing the plane into many regions, calculation of intersect points which are external to the pick window can be avoided. The Nicholl et al. method claims to speed up the non-trivial test, but it is complex to implement and requires performing many multiplication operations.
To summarize, it is a generally accepted that the Cohen-Sutherland technique is efficient for trivial testing, and alternate techniques are necessary to improve testing of line primitives that cannot be accepted or rejected using the Cohen-Sutherland trivial test.
The aforementioned methods generally attempt to achieve the goals of performing a minimum number of operations during testing so as to achieve speed, avoiding floating point calculations, particularly division calculations, and providing for simplified coding of the algorithm. However, none of these methods are able to achieve all of these goals. There is a clear need in graphic display for a line pick correlation method that can realize faster computations, fewer operations to test the lines and ease of coding.